{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/ods_stickers.jpg\" />\n",
    "    \n",
    "## [mlcourse.ai](https://mlcourse.ai) – Open Machine Learning Course \n",
    "\n",
    "<center >Author: Nikita Simonov (@simanjan)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <center>Self orginizing map.</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Self-organizing map is type of [neural network](https://en.wikipedia.org/wiki/Artificial_neural_network) is trained using [unsupervised learning](https://en.wikipedia.org/wiki/Unsupervised_learning) and also is an one of Kohonen neural network. The idea of creatins the such networks belongs to the Finnish scientist [Teuvo Kohonen](https://en.wikipedia.org/wiki/Teuvo_Kohonen). Basically that networks perform clustering and data visualization tasks. But they also allow to reduce multidimensional data into a space of a smaller dimension, and are used to search for patterns in the data.\n",
    "\n",
    "In this article we will see how to solve the clustering problem with help of the Kohonen network and will build self organizing map.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <center>Kohonen neural network.</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main element of the network is the Kohonen layer consists of a number of linear elements has m inputs. Every layer get on input the $x = (x_1, x_2, ... , x_n)$ vector from input data. The output of every layer is\n",
    "$$y_j = \\sum_i^n w_{ij}x_i $$\n",
    "\n",
    "- $i$ - number of input.\n",
    "- $j$ - number of layer (number of neuron).\n",
    "- $w_{ij}$ - weight of i-input j-layer.  \n",
    "\n",
    "\n",
    "After the $y$ of each neuron is calculated, the winner’s neuron will be determined according to the “winner takes all” rule. The max $$y_{max} = argmax\\{y_j\\}$$  is searched among all and then the output of such a neuron will be $1$, all other outputs will be $0$. \n",
    "If the max is  reached in several neurons:  \n",
    "- all signals will be equal to $1$.\n",
    "- the first in the max list will be $1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <center>Kohonen map.</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " - **Inizialization**\n",
    " \n",
    "     The most popular ways to set the initial node weights are:\n",
    "\n",
    "     - Set the random values to all weights.\n",
    "     - To take random $x_i$ from the input data and set it into weights.\n",
    "     - The choice of weight vectors from  from main components [(PCA)](https://en.wikipedia.org/wiki/Principal_component_analysis) of the input data set.\n",
    "  \n",
    "  As a result, we get $M_k$ is the map of neurons. $k$- neurons, their count is sets by the an analytics.\n",
    "  \n",
    "      $N$ - number of input data.\n",
    "    \n",
    " - **Trainning**\n",
    " \n",
    "    Initializing $t=0$ is it number of iteration and shuffling input data.\n",
    "    \n",
    "     - Choosing $x(t)$ from input data. \n",
    "     - Calculate distance  $$d_i(x(t), m_i(t)) = \\sqrt{(x_1(t) - m_{1i}(t))^2 + (x_2(t) - m_{2i}(t))^2 + ... + (x_n(t) - m_{ni}(t))^2}$$ from the input vector to all neurons of the map. Here:\n",
    "          - $d_i(x(t), m_i(t))$ is [Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance).\n",
    "          - $x(t)$ is input vector.\n",
    "          - $m_i \\in M_k$ \n",
    "     \n",
    "     Аmong all the neurons, it is determined closest to the incoming vector $d_{min} = argmin\\{d_i\\}$.The neuron associated to the $d_{min}$ will be the winner. If $d_{min}$ is reached at several neurons the winner will chosen randomly. $m_w$ is  winner neuron.\n",
    "     \n",
    "    Kohonen maps, unlike networks, use the \"Winner Takes Most\" algorithm in training. In this way the weights of not only the neuron of the winner, but also of [topologically](https://en.wikipedia.org/wiki/Topology) close neurons are updated.\n",
    "   \n",
    "     - Calculate $h$ function that defines the \"measure of neighborhood\" for neurons. Typically $h$ is the [Gaussian function](https://en.wikipedia.org/wiki/Gaussian_function). $$h_{wi} = \\alpha(t)  \\exp(-\\frac{||m_w - m_i||^2}{2 \\gamma(t) ^ 2})  $$ \n",
    "          - $m_w$ is winner neuron.\n",
    "          - $m_i \\in M_k$ is neuron from map.\n",
    "          - $\\gamma(t)$ is the value function the number of neighbors. The most commonly used function is linearly decreasing from the training itaration number. The value on the first iteration sets by the analyst. Also in simple version $\\gamma(t) = \\alpha(t)$.\n",
    "          - $\\alpha(t)$ is learning rate function. In simple version is constant. But for the best result, the function is often used $$\\alpha(t) = \\frac{A}{t + B}$$ here \n",
    "              - $t$ is number of iteration.\n",
    "              - $A and B$ is constant.\n",
    "          \n",
    "  - Change weights.\n",
    "      \n",
    "      Calculate $m_i(t) = m_i(t-1) + h_i(t) (x(t) - m_i(t-1)),     i = 1,2,..., k$.\n",
    "      \n",
    "      \n",
    "  Update the weights of all neurons that are neighbors of the winner's neuron.\n",
    "  Increase $t$ and repeat learning.\n",
    "\n",
    "  Training continues until $t < N$  or until the error becomes small."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://upload.wikimedia.org/wikipedia/commons/9/91/Somtraining.svg\" alt=\"Self orginizing map\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Self-organizing maps uses in [data mining](https://en.wikipedia.org/wiki/Data_mining) like a text analysis, financial statement analysis or image analysis.\n",
    "\n",
    "The advantages of self-organizing cards:\n",
    "    - Dimensionality reduction.\n",
    "    - Topological modeling of the training set.\n",
    "    - Resistance to outliers and missed data.\n",
    "    - Simple visualization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Visualization of the work of the self-organizing card.\n",
    "<img src=\"https://annalyzin.files.wordpress.com/2017/11/som-iterateanimate.gif?w=620\" alt=\"Self orginizing map\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets see small example.\n",
    "\n",
    "First we should install the 'SOMPY' library. The \"SOMPY\" does not have an official documentation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip3 install git+https://github.com/compmonks/SOMPY.git"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also you may need to install ipdb."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip3 install ipdb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Import all necessary libraries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pylab as plt\n",
    "\n",
    "%matplotlib inline\n",
    "import warnings\n",
    "\n",
    "warnings.filterwarnings(\"ignore\")\n",
    "from time import time\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import sompy\n",
    "\n",
    "np.random.seed(17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Creating a \"toy\" dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_len = 200\n",
    "\n",
    "data_frame_1 = pd.DataFrame(data=np.random.rand(data_len, 4))\n",
    "data_frame_1.values[:, 1] = (\n",
    "    data_frame_1.values[:, 1] + 0.42 * np.random.rand(data_len, 1)\n",
    ")[:, 0]\n",
    "\n",
    "data_frame_2 = pd.DataFrame(data=np.random.rand(data_len, 4) + 1)\n",
    "data_frame_2.values[:, 1] = (\n",
    "    -1 * data_frame_2.values[:, 1] + 0.62 * np.random.rand(data_len, 1)\n",
    ")[:, 0]\n",
    "\n",
    "data_frame_3 = pd.DataFrame(data=np.random.rand(data_len, 4) + 2)\n",
    "data_frame_3.values[:, 1] = (\n",
    "    0.5 * data_frame_3.values[:, 1] + 1 * np.random.rand(data_len, 1)\n",
    ")[:, 0]\n",
    "\n",
    "data_frame_4 = pd.DataFrame(data=np.random.rand(data_len, 4) + 3.5)\n",
    "data_frame_4.values[:, 1] = (\n",
    "    -0.1 * data_frame_4.values[:, 1] + 0.5 * np.random.rand(data_len, 1)\n",
    ")[:, 0]\n",
    "\n",
    "data_full = np.concatenate((data_frame_1, data_frame_2, data_frame_3, data_frame_4))\n",
    "\n",
    "fig = plt.figure()\n",
    "plt.plot(data_full[:, 0], data_full[:, 1], \"ob\", alpha=0.2, markersize=4)\n",
    "fig.set_size_inches(7, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data_full"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we need to set the size of the map, the set of toy data is small, so first we will set the small size of the map."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mapsize = [2, 2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The <code>build</code> method from SOMFactory creates self organizing map,  give it the size of the map and the data. the method takes the size of the map and the data.\n",
    "\n",
    "<code>initialization='random'</code> is a type of initial node weights, the random values to all weights."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "som = sompy.SOMFactory.build(data_full, mapsize, initialization=\"random\")\n",
    "som.train(n_job=1, verbose=\"info\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For visualizaion used mapview.View2DPacked."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = sompy.mapview.View2DPacked(10, 10, \"example\", text_size=8)\n",
    "v.show(som)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The som could recognize four clusters. Although the scope of the cluster are far from ideal.\n",
    "\n",
    "The \"cluster\" method is using [sklearn.Kmeans](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html) for predict clusters on the raw data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = sompy.mapview.View2DPacked(5, 5, \"test\", text_size=8)\n",
    "som.cluster(n_clusters=4)\n",
    "som.cluster_labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v.show(som, what=\"cluster\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at the visualization of clusters on the grid. For this use HitMapView."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = sompy.hitmap.HitMapView(8, 8, \"hitmap\", text_size=8, show_text=True)\n",
    "h.show(som);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The grid of self organizing map have a two types:\n",
    "    - square grid\n",
    "    - hexagonal grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://annalyzin.files.wordpress.com/2017/10/som-sqhex.png?w=650&h=238\" alt=\"Self orginizing map\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will create a new SOM and add some arguments for best result.\n",
    "\n",
    "Increasing map size."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mapsize = [20, 20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<code>lattice='rect'</code> is a square grid of SOM.\n",
    "\n",
    "<code>normalization='var'</code> is the type of [normalization](https://en.wikipedia.org/wiki/Normalization_(statistics)) of the input data. 'var' is [t-statistic](https://en.wikipedia.org/wiki/T-statistic).\n",
    "$$\\frac{X-\\bar{X}}{s}$$\n",
    "- $X$ is input data.\n",
    "- $\\bar{X}$ is average of input data.\n",
    "- $s$ is [standard deviation](https://en.wikipedia.org/wiki/Standard_deviation).\n",
    "\n",
    "<code>initialization='pca'</code> is a type of initial node weights, principal component initialization.\n",
    "\n",
    "<code>neighborhood='gaussian'</code> use the 'gaussian' function for \"measure of neighborhood\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "som = sompy.SOMFactory.build(\n",
    "    data_full,\n",
    "    mapsize,\n",
    "    lattice=\"rect\",\n",
    "    normalization=\"var\",\n",
    "    initialization=\"random\",\n",
    "    neighborhood=\"gaussian\",\n",
    ")\n",
    "som.train(n_job=1, verbose=\"info\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = sompy.mapview.View2DPacked(10, 10, \"example\", text_size=8)\n",
    "v.show(som)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = sompy.mapview.View2DPacked(5, 5, \"test\", text_size=8)\n",
    "som.cluster(n_clusters=4)\n",
    "som.cluster_labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = sompy.hitmap.HitMapView(8, 8, \"hitmap\", text_size=8, show_text=True)\n",
    "h.show(som);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's use the SOM for [the Iris Dataset](https://scikit-learn.org/stable/auto_examples/datasets/plot_iris_dataset.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iris = datasets.load_iris()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iris.target_names"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mapsize = [20, 20]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iris.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "som = sompy.SOMFactory.build(\n",
    "    iris.data,\n",
    "    mapsize,\n",
    "    lattice=\"rect\",\n",
    "    normalization=\"var\",\n",
    "    initialization=\"random\",\n",
    "    neighborhood=\"gaussian\",\n",
    ")\n",
    "som.train(n_job=1, verbose=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = sompy.mapview.View2DPacked(10, 10, \"iris\", text_size=8)\n",
    "v.show(som, which_dim=[0, 1, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The raw data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "view2D = sompy.mapview.View2D(10, 10, \"Iris_raw_data\", text_size=8)\n",
    "view2D.show(som, col_sz=4, which_dim=\"all\", desnormalize=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After training, SOM separates four distinct clusters, which is true."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "iris.data.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Visualization of a grid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = sompy.mapview.View2DPacked(5, 5, \"test\", text_size=8)\n",
    "som.cluster(n_clusters=3)\n",
    "som.cluster_labels"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = sompy.hitmap.HitMapView(8, 8, \"hitmap_iris\", text_size=8, show_text=True)\n",
    "h.show(som,);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also we can build the [U-matrix](https://en.wikipedia.org/wiki/U-matrix). Use umatrix.UMatrixView for visualization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "u = sompy.umatrix.UMatrixView(20, 20, \"umatrix\")\n",
    "UMAT = u.build_u_matrix(som)\n",
    "UMAT = u.show(som)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <center>Conclusion</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unfortunately, it’s impossible to consider the example of a hexagonal grid, because the library does not have the corresponding implementation. Also <code>normalization='var'</code> is only one implementation of the normalization.\n",
    "\n",
    "Kohonen self-organizing maps solve many issues and are a powerful tool for data analysis. In this article, we learned the principle of the SOM, as well as considered small examples of clustering and data visualization. But at the moment, the SOM is losing its popularity in favor of other algorithms."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
